package work;

import java.util.*;

public class Test05 {
    public static void main(String[] args) {
        new Solution0005_1().maxPoints(6,new int[]{8, 3, 7, 5, 6, 2},new int[][]{{1, 0},{2, 1},{3, 1},{4, 2}},3);
    }
}

class Solution0005_1 {
    int max=0;

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型 服务总数
     * @param points int整型一维数组 服务对应积分
     * @param dependencies int整型二维数组 服务依赖
     * @param k int整型 可买服务数量
     * @return int整型
     */
    public int maxPoints (int n, int[] points, int[][] dependencies, int k) {
        // write code here

        boolean[] records = new boolean[n];
        Arrays.fill(records,true);
        HashMap<Integer,List<Integer>> map = new HashMap<>();
        for (int[] dependency : dependencies) {
            int now = dependency[0];
            List<Integer> list = map.getOrDefault(dependency[1], new ArrayList<>());
            list.add(now);
            map.put(dependency[1],list);
            records[now]=false;
        }

        back(records,map,points,k,n,0);
        return max;
    }

    public void back(boolean[] records,HashMap<Integer,List<Integer>> map,int[] points,int k,int n,int value){
        if (k--<=0){
            System.out.println(max);
            max=Math.max(value,max);
            return;
        }

        for (int i = 0; i < n; i++) {
            boolean record = records[i];
            if (record){
                records[i]=false;
                List<Integer> list = map.get(i);
                if (list!=null){
                    for (Integer integer : list) {
                        records[integer]=true;
                    }
                }

                back(records,map,points,k,n,value+points[i]);

                if (list!=null){
                    for (Integer integer : list) {
                        records[integer]=false;
                    }
                }
                records[i]=true;
            }
        }


    }
}
